package jianzhioffer;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/24 9:53
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 */
public class offer53_ii_0_n_1中确实的数字 {

    public static void main(String[] args) {
//        int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 9};
        int[] nums = {0};
        System.out.println(missingNumber(nums));
    }

//    暴力遍历,不推荐
    public static int missingNumber1(int[] nums) {
        int count = 0;
        for (int i=0; i<nums.length; i++){
            if (nums[i] != i) return i;
            else count = i+1;
        }
     return count;
    }

//    二分查找
    public static int missingNumber(int[] nums) {
        int i = 0, j = nums.length-1;
        while (i<=j){
            int m = (i+j)/2;
            if (nums[m]==m){  // 在右半侧
                i = m + 1;
            }else {
                j = m - 1;
            }
        }
        return i;
    }
}
